{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Build Array Where You Can Find The Maximum Exactly K Comparisons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numOfArrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #生成数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定三个整数 <code>n</code>、<code>m</code> 和 <code>k</code> 。考虑使用下图描述的算法找出正整数数组中最大的元素。</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/04/19/e.png\" style=\"height: 372px; width: 424px;\" /></p>\n",
    "\n",
    "<p>请你构建一个具有以下属性的数组 <code>arr</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>arr</code> 中包含确切的&nbsp;<code>n</code> 个整数。</li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= m</code> 其中 <code>(0 &lt;= i &lt; n)</code> 。</li>\n",
    "\t<li>将上面提到的算法应用于 <code>arr</code>&nbsp;之后，<code>search_cost</code> 的值等于 <code>k</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回在满足上述条件的情况下构建数组 <code>arr</code> 的 <em>方法数量</em>&nbsp;，由于答案可能会很大，所以 <strong>必须</strong> 对 <code>10^9 + 7</code> 取余。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, m = 3, k = 1\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, m = 2, k = 3\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>没有数组可以满足上述条件\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 9, m = 1, k = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>唯一可能的数组是 [1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [build-array-where-you-can-find-the-maximum-exactly-k-comparisons](https://leetcode.cn/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [build-array-where-you-can-find-the-maximum-exactly-k-comparisons](https://leetcode.cn/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n3\\n1', '5\\n2\\n3', '9\\n1\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if m < k:\n",
    "            return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, curMax, cost):\n",
    "            if cost == 0:\n",
    "                return (curMax ** (n - i)) % MOD\n",
    "            if i == n:\n",
    "                return 0\n",
    "            \n",
    "            ans = curMax * dfs(i + 1, curMax, cost)\n",
    "            ans %= MOD\n",
    "            for nextNum in range(curMax + 1, m - cost + 2):\n",
    "                ans += dfs(i + 1, nextNum, cost - 1)\n",
    "                ans %= MOD\n",
    "            return ans\n",
    "        result = 0\n",
    "        \n",
    "        return dfs(0, 0, k)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        dp = [[0] * (m+1) for _ in range(k+1)]\n",
    "        for i in range(1,m+1): dp[1][i] = 1\n",
    "        for i in range(1,n):\n",
    "            for j in range(min(k,i+1),0,-1):\n",
    "                sm = sum(dp[j-1])\n",
    "                for p in range(m,j-1,-1):\n",
    "                    sm -= dp[j-1][p]\n",
    "                    dp[j][p] = (dp[j][p] * p + sm) % 1000000007\n",
    "        return sum(dp[-1]) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k > m or k == 0:\n",
    "            return 0\n",
    "        f = [[0] * (m + 1) for _ in range(k + 1)]\n",
    "        f2 = [[0] * (m + 1) for _ in range(k + 1)]\n",
    "        f[1][:] = range(m + 1)\n",
    "        for x in range(2, n + 1):\n",
    "            for y in range(1, k + 1):\n",
    "                for z in range(1, m + 1):\n",
    "                    f2[y][z] = (f2[y][z-1] + z * (f[y][z] - f[y][z-1]) + f[y-1][z-1]) % mod\n",
    "            f, f2 = f2, f\n",
    "        return f[k][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.MODULO = 10 ** 9 + 7\n",
    "\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        dp = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "        prefix = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "        prevDp = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "        prevPrefix = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for num in range(1, m + 1):\n",
    "            dp[num][1] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            if i > 1:\n",
    "                dp = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "\n",
    "            prefix = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "            for max_num in range(1, m + 1):\n",
    "                for cost in range(1, k + 1):\n",
    "                    answer = (max_num * prevDp[max_num][cost]) % self.MODULO\n",
    "                    answer = (answer + prevPrefix[max_num - 1][cost - 1]) % self.MODULO\n",
    "\n",
    "                    dp[max_num][cost] += answer\n",
    "                    dp[max_num][cost] %= self.MODULO\n",
    "\n",
    "                    prefix[max_num][cost] = (prefix[max_num - 1][cost] + dp[max_num][cost]) % self.MODULO\n",
    "\n",
    "            prevDp = dp\n",
    "            prevPrefix = prefix\n",
    "\n",
    "        retVal = prefix[m][k]\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.MODULO = 10 ** 9 + 7\n",
    "\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        dp = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "        for num in range(1, m + 1):\n",
    "            dp[num][1] = 1\n",
    "        prefix = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "        prevDp = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "        prevPrefix = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            if i > 1:\n",
    "                dp = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "\n",
    "            prefix = [[0] * (k + 1) for _ in range(m + 1)]\n",
    "            for max_num in range(1, m + 1):\n",
    "                for cost in range(1, k + 1):\n",
    "                    answer = (max_num * prevDp[max_num][cost]) % self.MODULO\n",
    "                    answer = (answer + prevPrefix[max_num - 1][cost - 1]) % self.MODULO\n",
    "\n",
    "                    dp[max_num][cost] += answer\n",
    "                    dp[max_num][cost] %= self.MODULO\n",
    "\n",
    "                    prefix[max_num][cost] = (prefix[max_num - 1][cost] + dp[max_num][cost]) % self.MODULO\n",
    "\n",
    "            prevDp = dp\n",
    "            prevPrefix = prefix\n",
    "\n",
    "        retVal = prefix[m][k]\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        c0, c1 = Counter(), Counter()\n",
    "        for i in range(1, m + 1):\n",
    "            c0[(i, 1)] = 1\n",
    "        for _ in range(1, n):\n",
    "            c1 = Counter()\n",
    "            for (ma, cost), cnt in c0.items():\n",
    "                c1[(ma, cost)] = (c1[(ma, cost)] + cnt * ma) % MOD\n",
    "                if cost >= k: continue\n",
    "                for i in range(ma + 1, m + 1):\n",
    "                    c1[(i, cost + 1)] = (c1[(i, cost + 1)] + cnt) % MOD\n",
    "            # End of loop\n",
    "            c0 = c1\n",
    "        return sum(cnt for (ma, cost), cnt in c0.items() if cost == k) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        #Cn-1 k-1\n",
    "        #第i个数，增大了j次，最大值等于k的数目\n",
    "        dp = [[[0] * m for _ in range(k)] for i in range(n)]\n",
    "        K = k\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(m):\n",
    "            dp[0][0][i] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(K):\n",
    "                for k in range(m):\n",
    "                    #j:j+1 k:k+1\n",
    "                    if j > 0:\n",
    "                        for l in range(k):\n",
    "                            dp[i][j][k] += dp[i-1][j-1][l]\n",
    "                    dp[i][j][k] += dp[i-1][j][k] * (k + 1)\n",
    "                    dp[i][j][k] %= mod\n",
    "            #print(dp[i])\n",
    "        return sum(dp[-1][-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        dp = [[[0 for _ in range(k + 1)] for _ in range(m + 1)] for _ in range(n)]\n",
    "        for j in range(1, m + 1):\n",
    "            dp[0][j][1] = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for kk in range(1, k + 1):\n",
    "                \n",
    "                acc = 0\n",
    "                for j in range(1, m + 1):\n",
    "\n",
    "                    dp[i][j][kk] = dp[i - 1][j][kk] * j + acc\n",
    "                    acc += dp[i - 1][j][kk - 1]\n",
    "\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        for line in dp[n - 1]:\n",
    "            ans += line[k]\n",
    "        return ans % 1000000007\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if(k>m):return 0\n",
    "        # f[i][j][k]=f[i-1][k-1<=j1<j][k-1]+f[i-1][j][k]*j\n",
    "        f=[[[0]*(k+1) for _0 in range(m+1)] for _1 in range(n+1)]\n",
    "        f[0][0][0],mod,ans=1,1000000007,0\n",
    "        for i in range(1,n+1):\n",
    "            for k1 in range(1,k+1):\n",
    "                for j in range(k1,m-k+k1+1):\n",
    "                    for j1 in range(k1-1,j):\n",
    "                        f[i][j][k1]+=f[i-1][j1][k1-1]\n",
    "                    f[i][j][k1]=(f[i][j][k1]+f[i-1][j][k1]*j)%mod\n",
    "        for i in range(k,m+1):ans+=f[n][i][k]\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if(k>m):return 0\n",
    "        # f[i][j][k]=f[i-1][k-1<=j1<j][k-1]+f[i-1][j][k]*j\n",
    "        f=[[[0]*(k+1) for _0 in range(m+1)] for _1 in range(n+1)]\n",
    "        f[0][0][0],mod,ans=1,1000000007,0\n",
    "        for i in range(1,n+1):\n",
    "            for k1 in range(1,k+1):\n",
    "                for j in range(k1,m-k+k1+1):\n",
    "                    f[i][j][k1]=(f[i][j-1][k1]-f[i-1][j-1][k1]*(j-1)+f[i-1][j-1][k1-1]+f[i-1][j][k1]*j)%mod\n",
    "        for i in range(k,m+1):ans+=f[n][i][k]\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        dp = [[[0]*(m+1) for _ in range(k+1)] for _ in range(n+1)]\n",
    "        for i in range(1, m+1):\n",
    "            dp[1][1][i] = 1\n",
    "        for i, j, h in product(range(1, n+1), range(1, k+1), range(m+1)):\n",
    "            dp[i][j][h] += (dp[i-1][j][h] * h + sum(dp[i-1][j-1][1:h])) % MOD\n",
    "        \n",
    "        return sum(dp[n][k][1:]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        # exception case\n",
    "        assert isinstance(n, int) and n >= 1\n",
    "        assert isinstance(m, int) and m >= 1\n",
    "        assert isinstance(k, int) and 0 <= k <= n\n",
    "        # main method: (Dynamic Programming)\n",
    "        return self._numOfArrays(n, m, k)\n",
    "\n",
    "    def _numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        assert isinstance(n, int) and n >= 1\n",
    "        assert isinstance(m, int) and m >= 1\n",
    "        assert isinstance(k, int) and 0 <= k <= n\n",
    "\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        dp = [[[0] * (m + 1) for _ in range(k + 1)] for __ in range(n + 1)]\n",
    "        MOD = int(1e9+7)\n",
    "\n",
    "        for j in range(1, m + 1):\n",
    "            dp[1][1][j] = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            for s in range(1, min(k, i) + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    dp[i][s][j] = dp[i - 1][s][j] * j\n",
    "                    for j0 in range(1, j):\n",
    "                        dp[i][s][j] += dp[i - 1][s - 1][j0]\n",
    "                    dp[i][s][j] %= MOD\n",
    "\n",
    "        res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # n 数组长度\n",
    "    # m 最大值\n",
    "    # k cost\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[[0] * m for _ in range(k + 1)] for _ in range(n)]\n",
    "        # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "        dp[0][1] = [1] * m\n",
    "        for i in range(1, n):\n",
    "            for p in range(1, k + 1):\n",
    "                for j in range(m):\n",
    "                    dp[i][p][j] = sum(dp[i - 1][p - 1][:j]) + dp[i - 1][p][j] * (j + 1)\n",
    "                    dp[i][p][j] %= MOD\n",
    "\n",
    "        return sum(dp[n - 1][k][:m]) % MOD\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     # n 数组长度\n",
    "#     # m 最大值\n",
    "#     # k cost\n",
    "#     def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "#         # 不存在搜索代价为 0 的数组\n",
    "#         if k == 0:\n",
    "#             return 0\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "#         # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "#         for j in range(1, m + 1):\n",
    "#             dp[1][1][j] = 1\n",
    "\n",
    "#         for i in range(2, n + 1):\n",
    "#             # 搜索代价不会超过数组长度\n",
    "#             for p in range(1, k + 1):\n",
    "#                 presum = 0\n",
    "#                 for j in range(1, m + 1):\n",
    "#                     dp[i][p][j] = (dp[i - 1][p][j] * j + presum) % MOD\n",
    "#                     presum += dp[i - 1][p - 1][j]\n",
    "\n",
    "#         # 最终的答案是所有 f[n][k][..] 的和\n",
    "#         # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "#         # res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "#         res = sum(dp[n][k][1 : m + 1]) % MOD\n",
    "#         return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     # n 数组长度\n",
    "#     # m 最大值\n",
    "#     # k cost\n",
    "#     def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "#         # 不存在搜索代价为 0 的数组\n",
    "#         if k == 0:\n",
    "#             return 0\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "#         # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "#         for j in range(1, m + 1):\n",
    "#             dp[1][1][j] = 1\n",
    "\n",
    "#         for i in range(2, n + 1):\n",
    "#             # 搜索代价不会超过数组长度\n",
    "#             for p in range(1, k + 1):\n",
    "#                 for j in range(1, m + 1):\n",
    "#                     dp[i][p][j] = dp[i - 1][p][j] * j\n",
    "#                     tmp = sum(dp[i - 1][p - 1][1:j])\n",
    "#                     dp[i][p][j] += tmp\n",
    "#                     dp[i][p][j] %= MOD\n",
    "\n",
    "#         # 最终的答案是所有 f[n][k][..] 的和\n",
    "#         # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "#         # res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "#         res = sum(dp[n][k][1 : m + 1]) % MOD\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# // dp[i][j][k]: 前i个最大不超过j更新k次的数组个数\n",
    "# // 分三种情况讨论\n",
    "# // 0~i无j: dp[i][j-1][k]种\n",
    "# // 0~i有j, 0~i-1无j, 则j在i: dp[i-1][j-1][k-1]种\n",
    "# // 0~i有j, 0~i-1有j, 则i位置值任意: j * (dp[i-1][j][k] - dp[i-1][j-1][k])种\n",
    "# // 边界条件:dp[0][0~m][0]=1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # n 数组长度\n",
    "    # m 最大值\n",
    "    # k cost\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        for j in range(1, m + 1):\n",
    "            dp[1][1][j] = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            for p in range(1, k + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    dp[i][p][j] = dp[i - 1][p][j] * j\n",
    "                    tmp = sum(dp[i - 1][p - 1][1:j])\n",
    "                    dp[i][p][j] += tmp\n",
    "                    dp[i][p][j] %= MOD\n",
    "\n",
    "        res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        dp = [[[0]*(m+1) for _ in range(k+1)] for _ in range(n+1)]\n",
    "        for i in range(1, m+1):\n",
    "            dp[1][1][i] = 1\n",
    "        for i, j, h in product(range(1, n+1), range(1, k+1), range(m+1)):\n",
    "            dp[i][j][h] += (dp[i-1][j][h] * h + sum(dp[i-1][j-1][1:h])) % MOD\n",
    "        \n",
    "        return sum(dp[n][k][1:]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# // dp[i][j][k]: 前i个最大不超过j更新k次的数组个数\n",
    "# // 分三种情况讨论\n",
    "# // 0~i无j: dp[i][j-1][k]种\n",
    "# // 0~i有j, 0~i-1无j, 则j在i: dp[i-1][j-1][k-1]种\n",
    "# // 0~i有j, 0~i-1有j, 则i位置值任意: j * (dp[i-1][j][k] - dp[i-1][j-1][k])种\n",
    "# // 边界条件:dp[0][0~m][0]=1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # n 数组长度\n",
    "    # m 最大值\n",
    "    # k cost\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for j in range(1, m + 1):\n",
    "            dp[1][1][j] = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            for p in range(1, k + 1):\n",
    "                presum = 0\n",
    "                for j in range(1, m + 1):\n",
    "                    dp[i][p][j] = (dp[i - 1][p][j] * j + presum) % MOD\n",
    "                    presum += dp[i - 1][p - 1][j]\n",
    "\n",
    "        res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     # n 数组长度\n",
    "#     # m 最大值\n",
    "#     # k cost\n",
    "#     def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "#         if k == 0:\n",
    "#             return 0\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "#         for j in range(1, m + 1):\n",
    "#             dp[1][1][j] = 1\n",
    "\n",
    "#         for i in range(2, n + 1):\n",
    "#             for p in range(1, k + 1):\n",
    "#                 for j in range(1, m + 1):\n",
    "#                     dp[i][p][j] = dp[i - 1][p][j] * j\n",
    "#                     tmp = sum(dp[i - 1][p - 1][1:j])\n",
    "#                     dp[i][p][j] += tmp\n",
    "#                     dp[i][p][j] %= MOD\n",
    "\n",
    "#         res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# // dp[i][j][k]: 前i个最大不超过j更新k次的数组个数\n",
    "# // 分三种情况讨论\n",
    "# // 0~i无j: dp[i][j-1][k]种\n",
    "# // 0~i有j, 0~i-1无j, 则j在i: dp[i-1][j-1][k-1]种\n",
    "# // 0~i有j, 0~i-1有j, 则i位置值任意: j * (dp[i-1][j][k] - dp[i-1][j-1][k])种\n",
    "# // 边界条件:dp[0][0~m][0]=1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # n 数组长度\n",
    "    # m 最大值\n",
    "    # k cost\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for j in range(1, m + 1):\n",
    "            dp[1][1][j] = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            for p in range(1, k + 1):\n",
    "                presum = 0\n",
    "                for j in range(1, m + 1):\n",
    "                    dp[i][p][j] = (dp[i - 1][p][j] * j + presum) % MOD\n",
    "                    presum += dp[i - 1][p - 1][j]\n",
    "\n",
    "        # res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "        res = sum(dp[n][k][1 : m + 1]) % MOD\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     # n 数组长度\n",
    "#     # m 最大值\n",
    "#     # k cost\n",
    "#     def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "#         if k == 0:\n",
    "#             return 0\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "#         for j in range(1, m + 1):\n",
    "#             dp[1][1][j] = 1\n",
    "\n",
    "#         for i in range(2, n + 1):\n",
    "#             for p in range(1, k + 1):\n",
    "#                 for j in range(1, m + 1):\n",
    "#                     dp[i][p][j] = dp[i - 1][p][j] * j\n",
    "#                     tmp = sum(dp[i - 1][p - 1][1:j])\n",
    "#                     dp[i][p][j] += tmp\n",
    "#                     dp[i][p][j] %= MOD\n",
    "\n",
    "#         res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        # 不存在搜索代价为 0 的数组\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        f = [[[0] * (m + 1) for _ in range(k + 1)] for __ in range(n + 1)]\n",
    "        mod = 10**9 + 7\n",
    "        # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "        for j in range(1, m + 1):\n",
    "            f[1][1][j] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            # 搜索代价不会超过数组长度\n",
    "            for s in range(1, min(k, i) + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    f[i][s][j] = f[i - 1][s][j] * j\n",
    "                    for j0 in range(1, j):\n",
    "                        f[i][s][j] += f[i - 1][s - 1][j0]\n",
    "                    f[i][s][j] %= mod\n",
    "        \n",
    "        # 最终的答案是所有 f[n][k][..] 的和\n",
    "        # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "        ans = sum(f[n][k][j] for j in range(1, m + 1)) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        # 不存在搜索代价为 0 的数组\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        f = [[[0] * (m + 1) for _ in range(k + 1)] for __ in range(n + 1)]\n",
    "        mod = 10**9 + 7\n",
    "        # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "        for j in range(1, m + 1):\n",
    "            f[1][1][j] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            # 搜索代价不会超过数组长度\n",
    "            for s in range(1, min(k, i) + 1):\n",
    "                # 前缀和\n",
    "                presum_j = 0\n",
    "                for j in range(1, m + 1):\n",
    "                    f[i][s][j] = (f[i - 1][s][j] * j + presum_j) % mod\n",
    "                    presum_j += f[i - 1][s - 1][j]\n",
    "        \n",
    "        # 最终的答案是所有 f[n][k][..] 的和\n",
    "        # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "        ans = sum(f[n][k][j] for j in range(1, m + 1)) % mod\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# // dp[i][j][k]: 前i个最大不超过j更新k次的数组个数\n",
    "# // 分三种情况讨论\n",
    "# // 0~i无j: dp[i][j-1][k]种\n",
    "# // 0~i有j, 0~i-1无j, 则j在i: dp[i-1][j-1][k-1]种\n",
    "# // 0~i有j, 0~i-1有j, 则i位置值任意: j * (dp[i-1][j][k] - dp[i-1][j-1][k])种\n",
    "# // 边界条件:dp[0][0~m][0]=1\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     # n 数组长度\n",
    "#     # m 最大值\n",
    "#     # k cost\n",
    "#     def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "#         if k == 0:\n",
    "#             return 0\n",
    "#         dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         for j in range(1, m + 1):\n",
    "#             dp[1][1][j] = 1\n",
    "\n",
    "#         for i in range(2, n + 1):\n",
    "#             for p in range(1, k + 1):\n",
    "#                 presum = 0\n",
    "#                 for j in range(1, m + 1):\n",
    "#                     dp[i][p][j] = (dp[i - 1][p][j] * j + presum) % MOD\n",
    "#                     presum += dp[i - 1][p - 1][j]\n",
    "\n",
    "#         # res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "#         res = sum(dp[n][k][1 : m + 1]) % MOD\n",
    "#         return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # n 数组长度\n",
    "    # m 最大值\n",
    "    # k cost\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        for j in range(1, m + 1):\n",
    "            dp[1][1][j] = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            for p in range(1, k + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    dp[i][p][j] = dp[i - 1][p][j] * j\n",
    "                    tmp = sum(dp[i - 1][p - 1][1:j])\n",
    "                    dp[i][p][j] += tmp\n",
    "                    dp[i][p][j] %= MOD\n",
    "\n",
    "        # res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "        res = sum(dp[n][k][1 : m + 1]) % MOD\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        dp = []\n",
    "        for i in range(n+1):\n",
    "            t = [[0] * (m+1) for _ in range(k+1)]\n",
    "            dp.append(t)\n",
    "        dp[0][0][0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(min(i, k) + 1):\n",
    "                for p in range(j, m+1):\n",
    "                    if j == 0:\n",
    "                        dp[i][j][p] = 0\n",
    "                    else:\n",
    "                        dp[i][j][p] = (p * dp[i-1][j][p] + sum(dp[i-1][j-1][:p])) % 1000000007\n",
    "        return (sum(dp[n][k]) % 1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        # 不存在搜索代价为 0 的数组\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        f = [[[0] * (m + 1) for _ in range(k + 1)] for __ in range(n + 1)]\n",
    "        mod = 10**9 + 7\n",
    "        # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "        for j in range(1, m + 1):\n",
    "            f[1][1][j] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            # 搜索代价不会超过数组长度\n",
    "            for s in range(1, min(k, i) + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    f[i][s][j] = f[i - 1][s][j] * j\n",
    "                    for j0 in range(1, j):\n",
    "                        f[i][s][j] += f[i - 1][s - 1][j0]\n",
    "                    f[i][s][j] %= mod\n",
    "        \n",
    "        # 最终的答案是所有 f[n][k][..] 的和\n",
    "        # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "        ans = sum(f[n][k][j] for j in range(1, m + 1)) % mod\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        # 不存在搜索代价为 0 的数组\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        f = [[[0] * (m + 1) for _ in range(k + 1)] for __ in range(n + 1)]\n",
    "        mod = 10**9 + 7\n",
    "        # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "        for j in range(1, m + 1):\n",
    "            f[1][1][j] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            # 搜索代价不会超过数组长度\n",
    "            for s in range(1, min(k, i) + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    f[i][s][j] = f[i - 1][s][j] * j\n",
    "                    for j0 in range(1, j):\n",
    "                        f[i][s][j] += f[i - 1][s - 1][j0]\n",
    "                    f[i][s][j] %= mod\n",
    "        \n",
    "        # 最终的答案是所有 f[n][k][..] 的和\n",
    "        # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "        ans = sum(f[n][k][j] for j in range(1, m + 1)) % mod\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        # 不存在搜索代价为 0 的数组\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        f = [[[0] * (m + 1) for _ in range(k + 1)] for __ in range(n + 1)]\n",
    "        mod = 10**9 + 7\n",
    "        # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "        for j in range(1, m + 1):\n",
    "            f[1][1][j] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            # 搜索代价不会超过数组长度\n",
    "            for s in range(1, min(k, i) + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    f[i][s][j] = f[i - 1][s][j] * j\n",
    "                    for j0 in range(1, j):\n",
    "                        f[i][s][j] += f[i - 1][s - 1][j0]\n",
    "                    f[i][s][j] %= mod\n",
    "        \n",
    "        # 最终的答案是所有 f[n][k][..] 的和\n",
    "        # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "        ans = sum(f[n][k][j] for j in range(1, m + 1)) % mod\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        f = [[[0] * (m + 1) for _ in range(k + 1)] for __ in range(n + 1)]\n",
    "        mod = 10**9 + 7\n",
    "        # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "        for j in range(1, m + 1):\n",
    "            f[1][1][j] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            # 搜索代价不会超过数组长度\n",
    "            for s in range(1, min(k, i) + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    f[i][s][j] = f[i - 1][s][j] * j\n",
    "                    for j0 in range(1, j):\n",
    "                        f[i][s][j] += f[i - 1][s - 1][j0]\n",
    "                    f[i][s][j] %= mod\n",
    "\n",
    "        # 最终的答案是所有 f[n][k][..] 的和\n",
    "        # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "        ans = sum(f[n][k][j] for j in range(1, m + 1)) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        # 不存在搜索代价为 0 的数组\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        f = [[[0] * (m + 1) for _ in range(k + 1)] for __ in range(n + 1)]\n",
    "        mod = 10**9 + 7\n",
    "        # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "        for j in range(1, m + 1):\n",
    "            f[1][1][j] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            # 搜索代价不会超过数组长度\n",
    "            for s in range(1, min(k, i) + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    f[i][s][j] = f[i - 1][s][j] * j\n",
    "                    for j0 in range(1, j):\n",
    "                        f[i][s][j] += f[i - 1][s - 1][j0]\n",
    "                    f[i][s][j] %= mod\n",
    "        \n",
    "        # 最终的答案是所有 f[n][k][..] 的和\n",
    "        # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "        ans = sum(f[n][k][j] for j in range(1, m + 1)) % mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\r\n",
    "        if k == 0: # 不存在搜尋代價為 0 的Array\r\n",
    "            return 0\r\n",
    "        # dp[i][s][j] 表示長度為 i，搜索代價為 s，最大值為 j 的Array的數量\r\n",
    "        dp = [[[0] * (m + 1) for _ in range(k + 1)] for __ in range(n + 1)]\r\n",
    "        MOD = 10**9 + 7\r\n",
    "        # base case，所有長度為 1 的Array的搜尋代價都為 1\r\n",
    "        for j in range(1, m + 1):\r\n",
    "            dp[1][1][j] = 1\r\n",
    "        for i in range(2, n + 1):\r\n",
    "            for s in range(1, min(k, i) + 1): # 搜尋代價不會超過Array長度\r\n",
    "                for j in range(1, m + 1): # 最大值\r\n",
    "                    # case 1: 沒有新的最大值，搜尋代價不變\r\n",
    "                    # 從長度為 i - 1 的情況轉移，且最後一個數字有 j 種選擇\r\n",
    "                    dp[i][s][j] = dp[i - 1][s][j] * j\r\n",
    "                    # case 2: 第 i 個數字是新的最大值，搜尋代價加 1\r\n",
    "                    # 從長度為 i - 1，搜尋代價為 s - 1 的，最大值為 1~j 的情況轉移\r\n",
    "                    for j0 in range(1, j):\r\n",
    "                        dp[i][s][j] += dp[i - 1][s - 1][j0]\r\n",
    "                    dp[i][s][j] %= MOD\r\n",
    "        # 最終的答案是所有 dp[n][k][..] 的和，即Array長度為 n，搜尋代價為 k，最大值任意\r\n",
    "        return sum(dp[n][k][j] for j in range(1, m + 1)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        dp = [[[0]*(m+1) for _ in range(k+1)] for _ in range(n+1)]\n",
    "        for i in range(1, m+1):\n",
    "            dp[1][1][i] = 1\n",
    "        for i, j, h in product(range(1, n+1), range(1, k+1), range(m+1)):\n",
    "            dp[i][j][h] += dp[i-1][j][h] * h % MOD + sum(dp[i-1][j-1][1:h]) % MOD\n",
    "        \n",
    "        return sum(dp[n][k][1:]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # n 数组长度\n",
    "    # m 最大值\n",
    "    # k cost\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        for j in range(1, m + 1):\n",
    "            dp[1][1][j] = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            for p in range(1, k + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    dp[i][p][j] = (\n",
    "                        sum(dp[i - 1][p - 1][:j]) + dp[i - 1][p][j] * j\n",
    "                    ) % MOD\n",
    "\n",
    "        return sum(dp[n][k][1 : m + 1]) % MOD\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     # n 数组长度\n",
    "#     # m 最大值\n",
    "#     # k cost\n",
    "#     def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "#         if k == 0:\n",
    "#             return 0\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         dp = [[[0] * m for _ in range(k + 1)] for _ in range(n)]\n",
    "#         # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "#         dp[0][1] = [1] * m\n",
    "#         for i in range(1, n):\n",
    "#             for p in range(1, k + 1):\n",
    "#                 # 1 <= m <= 100\n",
    "#                 # 所以要乘以 (j + 1)\n",
    "#                 for j in range(m):\n",
    "#                     dp[i][p][j] = sum(dp[i - 1][p - 1][:j]) + dp[i - 1][p][j] * (j + 1)\n",
    "#                     dp[i][p][j] %= MOD\n",
    "\n",
    "#         return sum(dp[n - 1][k][:m]) % MOD\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     # n 数组长度\n",
    "#     # m 最大值\n",
    "#     # k cost\n",
    "#     def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "#         # 不存在搜索代价为 0 的数组\n",
    "#         if k == 0:\n",
    "#             return 0\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "#         # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "#         for j in range(1, m + 1):\n",
    "#             dp[1][1][j] = 1\n",
    "\n",
    "#         for i in range(2, n + 1):\n",
    "#             # 搜索代价不会超过数组长度\n",
    "#             for p in range(1, k + 1):\n",
    "#                 presum = 0\n",
    "#                 for j in range(1, m + 1):\n",
    "#                     dp[i][p][j] = (dp[i - 1][p][j] * j + presum) % MOD\n",
    "#                     presum += dp[i - 1][p - 1][j]\n",
    "\n",
    "#         # 最终的答案是所有 f[n][k][..] 的和\n",
    "#         # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "#         # res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "#         res = sum(dp[n][k][1 : m + 1]) % MOD\n",
    "#         return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     # n 数组长度\n",
    "#     # m 最大值\n",
    "#     # k cost\n",
    "#     def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "#         # 不存在搜索代价为 0 的数组\n",
    "#         if k == 0:\n",
    "#             return 0\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "#         # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "#         for j in range(1, m + 1):\n",
    "#             dp[1][1][j] = 1\n",
    "\n",
    "#         for i in range(2, n + 1):\n",
    "#             # 搜索代价不会超过数组长度\n",
    "#             for p in range(1, k + 1):\n",
    "#                 for j in range(1, m + 1):\n",
    "#                     dp[i][p][j] = dp[i - 1][p][j] * j\n",
    "#                     tmp = sum(dp[i - 1][p - 1][1:j])\n",
    "#                     dp[i][p][j] += tmp\n",
    "#                     dp[i][p][j] %= MOD\n",
    "\n",
    "#         # 最终的答案是所有 f[n][k][..] 的和\n",
    "#         # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "#         # res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "#         res = sum(dp[n][k][1 : m + 1]) % MOD\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0 or k > m:\n",
    "            return 0\n",
    "        f = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, m + 1):\n",
    "            f[1][1][i] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            for s in range(1, min(k, i) + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    f[i][s][j] = f[i-1][s][j] * j\n",
    "                    for n in range(1, j):\n",
    "                        f[i][s][j] += f[i-1][s-1][n]\n",
    "                    f[i][s][j] %= mod\n",
    "\n",
    "        return sum(f[-1][-1][i] for i in range(1, m + 1)) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # n 数组长度\n",
    "    # m 最大值\n",
    "    # k cost\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[[0] * m for _ in range(k + 1)] for _ in range(n)]\n",
    "        dp[0][1] = [1] * m\n",
    "        for i in range(1, n):\n",
    "            for p in range(1, k + 1):\n",
    "                for j in range(m):\n",
    "                    dp[i][p][j] = sum(dp[i - 1][p - 1][:j]) + dp[i - 1][p][j] * (j + 1)\n",
    "                    dp[i][p][j] %= MOD\n",
    "        return sum(dp[n - 1][k][:m]) % MOD\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     # n 数组长度\n",
    "#     # m 最大值\n",
    "#     # k cost\n",
    "#     def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "#         if k == 0:\n",
    "#             return 0\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         dp = [[[0] * m for _ in range(k + 1)] for _ in range(n)]\n",
    "#         # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "#         dp[0][1] = [1] * m\n",
    "#         for i in range(1, n):\n",
    "#             for p in range(1, k + 1):\n",
    "#                 # 1 <= m <= 100\n",
    "#                 # 所以要乘以 (j + 1)\n",
    "#                 for j in range(m):\n",
    "#                     dp[i][p][j] = sum(dp[i - 1][p - 1][:j]) + dp[i - 1][p][j] * (j + 1)\n",
    "#                     dp[i][p][j] %= MOD\n",
    "\n",
    "#         return sum(dp[n - 1][k][:m]) % MOD\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     # n 数组长度\n",
    "#     # m 最大值\n",
    "#     # k cost\n",
    "#     def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "#         # 不存在搜索代价为 0 的数组\n",
    "#         if k == 0:\n",
    "#             return 0\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "#         # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "#         for j in range(1, m + 1):\n",
    "#             dp[1][1][j] = 1\n",
    "\n",
    "#         for i in range(2, n + 1):\n",
    "#             # 搜索代价不会超过数组长度\n",
    "#             for p in range(1, k + 1):\n",
    "#                 presum = 0\n",
    "#                 for j in range(1, m + 1):\n",
    "#                     dp[i][p][j] = (dp[i - 1][p][j] * j + presum) % MOD\n",
    "#                     presum += dp[i - 1][p - 1][j]\n",
    "\n",
    "#         # 最终的答案是所有 f[n][k][..] 的和\n",
    "#         # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "#         # res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "#         res = sum(dp[n][k][1 : m + 1]) % MOD\n",
    "#         return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     # n 数组长度\n",
    "#     # m 最大值\n",
    "#     # k cost\n",
    "#     def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "#         # 不存在搜索代价为 0 的数组\n",
    "#         if k == 0:\n",
    "#             return 0\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "#         # 边界条件，所有长度为 1 的数组的搜索代价都为 1\n",
    "#         for j in range(1, m + 1):\n",
    "#             dp[1][1][j] = 1\n",
    "\n",
    "#         for i in range(2, n + 1):\n",
    "#             # 搜索代价不会超过数组长度\n",
    "#             for p in range(1, k + 1):\n",
    "#                 for j in range(1, m + 1):\n",
    "#                     dp[i][p][j] = dp[i - 1][p][j] * j\n",
    "#                     tmp = sum(dp[i - 1][p - 1][1:j])\n",
    "#                     dp[i][p][j] += tmp\n",
    "#                     dp[i][p][j] %= MOD\n",
    "\n",
    "#         # 最终的答案是所有 f[n][k][..] 的和\n",
    "#         # 即数组长度为 n，搜索代价为 k，最大值任意\n",
    "#         # res = sum(dp[n][k][j] for j in range(1, m + 1)) % MOD\n",
    "#         res = sum(dp[n][k][1 : m + 1]) % MOD\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        dp = [[[0]*(m+1) for _ in range(k+1)] for _ in range(n+1)]\n",
    "        for i in range(1, m+1):\n",
    "            dp[1][1][i] = 1\n",
    "        for i, j, h in product(range(1, n+1), range(1, k+1), range(m+1)):\n",
    "            dp[i][j][h] += dp[i-1][j][h] * h\n",
    "            dp[i][j][h] += sum(dp[i-1][j-1][1:h])\n",
    "        \n",
    "        return sum(dp[n][k][1:]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        dp = [[[0]*(m+1) for _ in range(k+1)] for _ in range(n+1)]\n",
    "        for i in range(1, m+1):\n",
    "            dp[1][1][i] = 1\n",
    "        for i, j, h in product(range(1, n+1), range(1, k+1), range(m+1)):\n",
    "            dp[i][j][h] += dp[i-1][j][h] * h + sum(dp[i-1][j-1][1:h])\n",
    "        \n",
    "        return sum(dp[n][k][1:]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        \n",
    "        if k==0:\n",
    "            return 0\n",
    "        \n",
    "        MODX = 10**9+7\n",
    "        \n",
    "        dp = [[[0]*(m+1) for _ in range(k+1)] for _ in range(n+1)] \n",
    "\n",
    "        for j in range(1,m+1):\n",
    "            dp[1][1][j] = 1\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            for s in range(1,k+1):\n",
    "                for j in range(1,m+1):\n",
    "\n",
    "    \n",
    "                    dp[i][s][j]= dp[i-1][s][j]*j\n",
    "                    for j0 in range(1,j):\n",
    "                        dp[i][s][j] += dp[i-1][s-1][j0]  \n",
    "                    \n",
    "                    dp[i][s][j] %=MODX\n",
    "\n",
    "        #print(dp[n][k])\n",
    "        #print(dp[2][1][2])\n",
    "        return sum(dp[n][k])%MODX          \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0 or k > m:\n",
    "            return 0\n",
    "        f = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, m + 1):\n",
    "            f[1][1][i] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            for s in range(1, min(k, i) + 1):\n",
    "                pre = 0\n",
    "                for j in range(1, m + 1):\n",
    "                    f[i][s][j] = f[i-1][s][j] * j + pre\n",
    "                    pre += f[i-1][s-1][j]\n",
    "                    f[i][s][j] %= mod\n",
    "\n",
    "        return sum(f[-1][-1][i] for i in range(1, m + 1)) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0 or k > m:\n",
    "            return 0\n",
    "        f = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, m + 1):\n",
    "            f[1][1][i] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            for s in range(1, k + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    f[i][s][j] = f[i-1][s][j] * j\n",
    "                    for n in range(1, j):\n",
    "                        f[i][s][j] += f[i-1][s-1][n]\n",
    "                    f[i][s][j] %= mod\n",
    "\n",
    "        return sum(f[-1][-1][i] for i in range(1, m + 1)) % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        \n",
    "        if k==0:\n",
    "            return 0\n",
    "        \n",
    "        MODX = 10**9+7\n",
    "        \n",
    "        dp = [[[0]*(m+1) for _ in range(k+1)] for _ in range(n+1)] \n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for s in range(1,k+1):\n",
    "                for j in range(1,m+1):\n",
    "                    if i==1:\n",
    "                        if s==1:\n",
    "                            dp[i][s][j] = 1\n",
    "                        continue \n",
    "                    if j==1:\n",
    "                        if s==1:\n",
    "                            dp[i][s][j] = 1\n",
    "                        continue\n",
    "\n",
    "                    dp[i][s][j]= dp[i-1][s][j]*j\n",
    "                    for j0 in range(1,j):\n",
    "                        dp[i][s][j] += dp[i-1][s-1][j0]  \n",
    "                    \n",
    "                    dp[i][s][j] %=MODX\n",
    "\n",
    "        #print(dp[n][k])\n",
    "        #print(dp[2][1][2])\n",
    "        return sum(dp[n][k])%MODX          \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        f = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        mod = 10 ** 9 + 7\n",
    "        for j in range(1, m + 1):\n",
    "            f[1][1][j] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            for s in range(1, min(i, k) + 1):\n",
    "                for j in range(1, m + 1):\n",
    "                    f[i][s][j] = f[i - 1][s][j] * j\n",
    "                    for j0 in range(1, j):\n",
    "                        f[i][s][j] += f[i - 1][s - 1][j0]\n",
    "                    f[i][s][j] % mod\n",
    "        ans = sum(f[n][k][j] for j in range(1, m + 1)) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]\n",
    "        for maximum_value in range(m+1):\n",
    "            for now in range(n+1):\n",
    "                dp[now][maximum_value][k] = pow(maximum_value, n-now, MOD)\n",
    "        for now in range(n-1, -1, -1):\n",
    "            for maximum_value in range(m, -1, -1):\n",
    "                for search_cost in range(k-1, -1, -1):\n",
    "                    for i in range(1, m+1):\n",
    "                        dp[now][maximum_value][search_cost] += dp[now+1][maximum_value][search_cost] if i <= maximum_value else dp[now+1][i][search_cost+1]\n",
    "        return dp[0][0][0] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, cost: int) -> int:\n",
    "        if not cost:\n",
    "            return 0\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[[0] * (m + 1) for _ in range(cost + 1)] for _ in range(n + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            dp[1][1][i] = 1\n",
    "        \n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, cost + 1):\n",
    "                for k in range(1, m + 1):\n",
    "                    dp[i][j][k] = dp[i - 1][j][k] * k\n",
    "                    for p in range(1, k):\n",
    "                        dp[i][j][k] += dp[i - 1][j - 1][p]\n",
    "                dp[i][j][k] %= mod\n",
    "        \n",
    "        return sum(dp[-1][cost][k] for k in range(m + 1)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    线性DP\n",
    "    dp[i][j][k]表示长度为i的数组，要花费j的代价，找到其中最大值为k条件下所有能构造出的数组数量\n",
    "    三重循环最内层枚举的是最大元素值，状态转移时考虑，假设当前遍历到的最大元素值不是已遍历数组中最\n",
    "    大的（之前有大于等于它的），那么本次遍历就不会增加开销，当前位置可以放[1, k]中任意一个值\n",
    "    dp[i][j][k] = dp[i - 1][j][k] * k\n",
    "    如果当前遍历的值是最大值，那么前i - 1个元素的数组中最大值只能在[1, k - 1]之间，需要把这个区间\n",
    "    内所有的可能都加起来，且因为当前遍历的值是最大值，开销会增加1，那么前k - 1个元素的开销只有j - 1\n",
    "    dp[i][j][k] += dp[i - 1][j - 1][k']\n",
    "    '''\n",
    "    def numOfArrays(self, n: int, m: int, cost: int) -> int:\n",
    "        if not cost:\n",
    "            return 0\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[[0] * (m + 1) for _ in range(cost + 1)] for _ in range(n + 1)]\n",
    "        '''\n",
    "        按题意中的算法，对于只有一个元素的任意值，开销一定为1，对应的构建数组可能也是1\n",
    "        '''\n",
    "        for i in range(1, m + 1):\n",
    "            dp[1][1][i] = 1\n",
    "        \n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, cost + 1):\n",
    "                for k in range(1, m + 1):\n",
    "                    dp[i][j][k] = dp[i - 1][j][k] * k\n",
    "                    for p in range(1, k):\n",
    "                        dp[i][j][k] += dp[i - 1][j - 1][p]\n",
    "                dp[i][j][k] %= mod\n",
    "        \n",
    "        '''\n",
    "        需要把最大值在[1, m]内的所有可能数组都统计出来\n",
    "        '''\n",
    "        return sum(dp[-1][cost][k] for k in range(m + 1)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    线性DP\n",
    "    dp[i][j][k]表示长度为i的数组，要花费j的代价，找到其中最大值为k条件下所有能构造出的数组数量\n",
    "    三重循环最内层枚举的是最大元素值，状态转移时考虑，假设当前遍历到的最大元素值不是已遍历数组中最\n",
    "    大的（之前有大于等于它的），那么本次遍历就不会增加开销，当前位置可以放[1, k]中任意一个值\n",
    "    dp[i][j][k] = dp[i - 1][j][k] * k\n",
    "    如果当前遍历的值是最大值，那么前i - 1个元素的数组中最大值只能在[1, k - 1]之间，需要把这个区间\n",
    "    内所有的可能都加起来，且因为当前遍历的值是最大值，开销会增加1，那么前k - 1个元素的开销只有j - 1\n",
    "    dp[i][j][k] += dp[i - 1][j - 1][k']\n",
    "    '''\n",
    "    def numOfArrays(self, n: int, m: int, cost: int) -> int:\n",
    "        if not cost:\n",
    "            return 0\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[[0] * (m + 1) for _ in range(cost + 1)] for _ in range(n + 1)]\n",
    "        # prefix = [[0] * (cost + 1) for _ in range(n + 1)]\n",
    "        '''\n",
    "        按题意中的算法，对于只有一个元素的任意值，开销一定为1，对应的构建数组可能也是1\n",
    "        '''\n",
    "        for i in range(1, m + 1):\n",
    "            dp[1][1][i] = 1\n",
    "            # prefix[1][1] += 1\n",
    "        \n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, min(m, cost) + 1):\n",
    "                prefix = 0\n",
    "                for k in range(1, m + 1):\n",
    "                    dp[i][j][k] = dp[i - 1][j][k] * k + prefix\n",
    "                    prefix += dp[i - 1][j - 1][k]\n",
    "                    # dp[i][j][k] = dp[i - 1][j][k] * k + prefix[i - 1][j - 1]\n",
    "                    # prefix[i][j] += dp[i][j][k]\n",
    "\n",
    "                #     dp[i][j][k] = dp[i - 1][j][k] * k\n",
    "                #     for p in range(1, k):\n",
    "                #         dp[i][j][k] += dp[i - 1][j - 1][p]\n",
    "                # dp[i][j][k] %= mod\n",
    "        \n",
    "        # print(dp)\n",
    "        # print(prefix)\n",
    "        '''\n",
    "        需要把最大值在[1, m]内的所有可能数组都统计出来\n",
    "        '''\n",
    "        return sum(dp[-1][cost][k] for k in range(m + 1)) % mod\n",
    "        # return prefix[-1][-1] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    线性DP\n",
    "    dp[i][j][k]表示长度为i的数组，要花费j的代价，找到其中最大值为k条件下所有能构造出的数组数量\n",
    "    三重循环最内层枚举的是最大元素值，状态转移时考虑，假设当前遍历到的最大元素值不是已遍历数组中最\n",
    "    大的（之前有大于等于它的），那么本次遍历就不会增加开销，当前位置可以放[1, k]中任意一个值\n",
    "    dp[i][j][k] = dp[i - 1][j][k] * k\n",
    "    如果当前遍历的值是最大值，那么前i - 1个元素的数组中最大值只能在[1, k - 1]之间，需要把这个区间\n",
    "    内所有的可能都加起来，且因为当前遍历的值是最大值，开销会增加1，那么前k - 1个元素的开销只有j - 1\n",
    "    dp[i][j][k] += dp[i - 1][j - 1][k']\n",
    "    '''\n",
    "    def numOfArrays(self, n: int, m: int, cost: int) -> int:\n",
    "        if not cost:\n",
    "            return 0\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[[0] * (m + 1) for _ in range(cost + 1)] for _ in range(n + 1)]\n",
    "        '''\n",
    "        按题意中的算法，对于只有一个元素的任意值，开销一定为1，对应的构建数组可能也是1\n",
    "        '''\n",
    "        for i in range(1, m + 1):\n",
    "            dp[1][1][i] = 1\n",
    "        \n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(1, min(m, cost) + 1):\n",
    "                '''\n",
    "                prefix为dp[i - 1][j - 1][p] p∈[1, k - 1]的前缀和，从而减少一次\n",
    "                注释内的循环累加操作\n",
    "                '''\n",
    "                prefix = 0\n",
    "                for k in range(1, m + 1):\n",
    "                    dp[i][j][k] = dp[i - 1][j][k] * k + prefix\n",
    "                    prefix += dp[i - 1][j - 1][k]\n",
    "\n",
    "                #     dp[i][j][k] = dp[i - 1][j][k] * k\n",
    "                #     for p in range(1, k):\n",
    "                #         dp[i][j][k] += dp[i - 1][j - 1][p]\n",
    "                # dp[i][j][k] %= mod\n",
    "        \n",
    "        '''\n",
    "        需要把最大值在[1, m]内的所有可能数组都统计出来\n",
    "        '''\n",
    "        return sum(dp[-1][cost][k] for k in range(m + 1)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j, c): # 第i位, k=j, max=c\n",
    "            if j > i or j == 0: return 0\n",
    "            if i == 1: return 1\n",
    "            return (sum(dp(i-1, j-1, d) for d in range(1, c)) + dp(i-1, j, c) * c) % (10**9+7)\n",
    "        return sum(dp(n, k, c) for c in range(1, m+1)) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j, c): # 第i位, k=j, max=c\n",
    "            if j > i or j == 0: return 0\n",
    "            if i == 1: return 1\n",
    "            return (sum(dp(i-1, j-1, d) for d in range(1, c)) + dp(i-1, j, c) * c) % (10**9+7)\n",
    "        return sum(dp(n, k, c) for c in range(1, m+1)) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        mod = int(10**9 + 7)\n",
    "        @cache\n",
    "        def dp(i, v, k):\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            if v and i > k:\n",
    "                ans += dp(i - 1, v, k) * v\n",
    "            if k:\n",
    "                for x in range(v + 1, m - k + 2):\n",
    "                    ans += dp(i - 1, x, k - 1)\n",
    "            return ans % mod\n",
    "        return dp(n, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "\n",
    "        @cache\n",
    "        def gettimes(s,t):\n",
    "            #s**t\n",
    "            if t==0:\n",
    "                return 1\n",
    "            return (s*gettimes(s,t-1))%mod\n",
    "\n",
    "        @cache\n",
    "        def getcount(idx,premax,search_cost):\n",
    "            #print(idx,premax,search_cost)\n",
    "            if idx == n:\n",
    "                if search_cost==1:\n",
    "                    if premax<m:\n",
    "                        return m-premax\n",
    "                    return 0\n",
    "                elif search_cost==0:\n",
    "                    return premax\n",
    "                else:\n",
    "                    return 0\n",
    "            if m-premax<search_cost:\n",
    "                return 0\n",
    "            elif search_cost==0:\n",
    "                return gettimes(premax,n-idx+1)\n",
    "            ans = 0\n",
    "            ans += premax*getcount(idx+1,premax,search_cost)\n",
    "            ans %= mod\n",
    "            cur = premax+1\n",
    "            while cur<=m:\n",
    "                subans = getcount(idx+1,cur,search_cost-1)\n",
    "                if subans ==0:\n",
    "                    break\n",
    "                ans += subans\n",
    "                ans %= mod\n",
    "                cur += 1\n",
    "            return ans\n",
    "\n",
    "        return getcount(1,0,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        # dp = [[[1]*(n+2)]*(k+2)]*(m+2)\n",
    "        import numpy as np\n",
    "        dp=np.zeros((m+2,k+2,n+2), dtype = np.int64)\n",
    "        dp[0][0][0]=1\n",
    "\n",
    "\n",
    "        # for i in range(1,m+1):\n",
    "        #     for j in range(1,min(k,i)+1):\n",
    "        #         dp[i][j][j]=self.C(i,j)\n",
    "        for j in range(1,k+1):\n",
    "            for i in range(j,n+1):\n",
    "                cum=0\n",
    "                for s in range(j,m+1):\n",
    "                    cum=(cum+dp[s-1][j-1][i-1])%int(1e9+7)\n",
    "                    dp[s][j][i]=((dp[s][j][i-1]*s)%int(1e9+7)+cum)%int(1e9+7)\n",
    "\n",
    "\n",
    "        return int((dp.sum(axis=0))[k][n])%int(1e9+7)\n",
    "        \n",
    "    def C(self, a: int, b: int) -> int:\n",
    "        ans=1\n",
    "        div=1\n",
    "        for i in range(b):\n",
    "            ans=(ans*(a-i))%int(1e9+7)\n",
    "            div=(div*(i+1))%int(1e9+7)\n",
    "        return ans//div"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def dfs(i, v, cost):\n",
    "            if cost > k:\n",
    "                return 0\n",
    "            if i == n-1:\n",
    "                return int(cost==k)\n",
    "            \n",
    "            t = dfs(i+1, v, cost) * v\n",
    "            for j in range(v+1,m+1):\n",
    "                t += dfs(i+1, j, cost+1)\n",
    "                \n",
    "            return t % MOD\n",
    "        \n",
    "        ans = 0\n",
    "        for j in range(1,m+1):\n",
    "            ans += dfs(0, j, 1)\n",
    "        return ans % MOD\n",
    "                    \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def dfs(i, v, cost):\n",
    "            if cost > k:\n",
    "                return 0\n",
    "            if i == n-1:\n",
    "                return int(cost==k)\n",
    "            \n",
    "            t = 0\n",
    "            for j in range(1,m+1):\n",
    "                if j > v:\n",
    "                    t += dfs(i+1, j, cost+1)\n",
    "                else:\n",
    "                    t += dfs(i+1, v, cost)\n",
    "            return t % MOD\n",
    "        \n",
    "        ans = 0\n",
    "        for j in range(1,m+1):\n",
    "            ans += dfs(0, j, 1)\n",
    "        return ans % MOD\n",
    "                    \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i, s, j):\n",
    "            if s == 0:\n",
    "                return 0\n",
    "            if i == 1:\n",
    "                if s == 1:\n",
    "                    return 1\n",
    "                return 0\n",
    "            res = j * dfs(i-1, s, j)\n",
    "            for j2 in range(1, j):\n",
    "                res += dfs(i-1, s-1, j2)\n",
    "            return res % M\n",
    "        return sum(dfs(n, k, i) for i in range(1, m+1)) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param m:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def get_cnt(cur_len, cur_val, cur_cost):\n",
    "            if cur_cost > k:\n",
    "                return 0\n",
    "            if cur_len == n:\n",
    "                return 1 if cur_cost == k else 0\n",
    "            ret = 0\n",
    "            for i in range(1, m+1):\n",
    "                if i > cur_val:\n",
    "                    ret += get_cnt(cur_len+1, i, cur_cost+1) % (10**9+7)\n",
    "                else:\n",
    "                    ret += get_cnt(cur_len+1, cur_val, cur_cost) % (10**9+7)\n",
    "            return ret % (10**9+7)\n",
    "\n",
    "        return get_cnt(0, -1, 0) % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param m:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def get_cnt(cur_len, cur_val, cur_cost):\n",
    "            if cur_cost > k:\n",
    "                return 0\n",
    "            if cur_len == n:\n",
    "                return 1 if cur_cost == k else 0\n",
    "            ret = 0\n",
    "            for i in range(1, m+1):\n",
    "                if i > cur_val:\n",
    "                    ret += get_cnt(cur_len+1, i, cur_cost+1) % (10**9+7)\n",
    "                else:\n",
    "                    ret += get_cnt(cur_len+1, cur_val, cur_cost) % (10**9+7)\n",
    "            return ret % (10**9+7)\n",
    "\n",
    "        return get_cnt(0, 0, 0) % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "\n",
    "       @cache\n",
    "       def dfs(i: int, maximum: int, j: int) -> int:\n",
    "          if i == n:\n",
    "             return j == k\n",
    "          if j == k:\n",
    "             return pow(maximum, n - i, MOD)\n",
    "          res = maximum * dfs(i + 1, maximum, j) % MOD\n",
    "          for x in range(maximum + 1, m + 1):\n",
    "             res += dfs(i + 1, x, j + 1)\n",
    "             res %= MOD\n",
    "          return res\n",
    "       return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "\n",
    "       @cache\n",
    "       def dfs(i: int, maximum: int, j: int) -> int:\n",
    "          if i == n:\n",
    "             return j == k\n",
    "          if j == k:\n",
    "             return pow(maximum, n - i, MOD)\n",
    "          res = 0\n",
    "          for x in range(1, m + 1):\n",
    "             if x <= maximum:\n",
    "                res += dfs(i + 1, maximum, j)\n",
    "             else:\n",
    "                res += dfs(i + 1, x, j + 1)\n",
    "             res %= MOD\n",
    "          return res\n",
    "       return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "mod = 10**9 + 7\n",
    "# res = dict()\n",
    "# # n = 50\n",
    "# # m = 100\n",
    "# # k = 50\n",
    "#\n",
    "#\n",
    "# @lru_cache(None)\n",
    "# def dfs(n, m, k):\n",
    "#     if n == 1:\n",
    "#         if k == 1:\n",
    "#             return m\n",
    "#         return 0\n",
    "#     if k == 0:\n",
    "#\n",
    "#\n",
    "#     return dfs(n-1, )\n",
    "# dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]\n",
    "# dp[0][0][0] = 1\n",
    "# for i in range(n):  # 个数\n",
    "#     pre = [[0]*(k+1) for _ in range(m+1)]\n",
    "#\n",
    "#     for x in range(m+1):  # 最大值\n",
    "#         for y in range(1, k+1):  # 代价\n",
    "#             dp[i+1][x][y] = dp[i][][y-1] + dp[i+1][][y]\n",
    "#\n",
    "#\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, ceil, cost):\n",
    "\n",
    "            if i == n:\n",
    "                return 1 if cost == k else 0\n",
    "\n",
    "            res = dfs(i + 1, ceil, cost) * ceil\n",
    "            if cost + 1 <= k:\n",
    "                res += sum(dfs(i + 1, cc, cost + 1) for cc in range(ceil + 1, m + 1))\n",
    "            return res % mod\n",
    "\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(array_size, max_num, cost):\n",
    "            if array_size == 0:\n",
    "                if cost == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if cost < 0:\n",
    "                return 0\n",
    "\n",
    "            total = 0\n",
    "            # The next number is less than or equal to the current max number\n",
    "            total += max_num * dfs(array_size - 1, max_num, cost) % MOD\n",
    "            # The next number is greater than the current max number\n",
    "            for next_max_num in range(max_num + 1, m + 1):\n",
    "                total += dfs(array_size - 1, next_max_num, cost - 1) % MOD\n",
    "            return total % MOD\n",
    "\n",
    "        return dfs(n, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        # the count of possible arrays that has array_size and max number is max_num, and its cost is exactly as cost\n",
    "        @lru_cache(None)\n",
    "        def dfs(array_size, max_num, cost):\n",
    "            if cost < 0:\n",
    "                return 0\n",
    "\n",
    "            if array_size == 0:\n",
    "                if cost == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            total = 0\n",
    "            # considering adding a new number into the array of size (array_size - 1)\n",
    "            # 1. if the new added number is not greater to the current max number\n",
    "            #    the new number range is [1, max_num], count = max_num\n",
    "            total += max_num * dfs(array_size - 1, max_num, cost) % MOD\n",
    "            # 2. if the next number is greater than the current max number\n",
    "            #    the new number range is [max_num + 1, m]\n",
    "            total += sum(\n",
    "                dfs(array_size - 1, next_max_num, cost - 1) % MOD\n",
    "                for next_max_num in range(max_num + 1, m + 1)\n",
    "            )\n",
    "            return total % MOD\n",
    "\n",
    "        return dfs(n, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def fun(now, search_cost, maximum_value):\n",
    "            if search_cost == k:\n",
    "                return pow(maximum_value, n-now, MOD)\n",
    "            if now == n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(1, m+1):\n",
    "                if i > maximum_value:\n",
    "                    res += fun(now+1, search_cost+1, i)\n",
    "                else:\n",
    "                    res += fun(now+1, search_cost, maximum_value)\n",
    "            return res\n",
    "        return fun(0, 0, 0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        @cache\n",
    "        def dfs(i, j, k):\n",
    "            if i == 0 or j == 0 or k == 0: \n",
    "                return 0\n",
    "            if i == 1 and k == 1: \n",
    "                return 1 \n",
    "\n",
    "            # j在此刻作为最大值\n",
    "            res = 0\n",
    "            for t in range(1, j):\n",
    "                res = (res + dfs(i-1, t, k-1)) % mod\n",
    "            # j之前作为最大值\n",
    "            res += j*dfs(i-1, j, k)\n",
    "            return res % mod \n",
    "        \n",
    "        return sum(dfs(n, i, k) for i in range(1, m+1)) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        @cache\n",
    "        def dfs(i, j, k):\n",
    "            if i == n or j == 0 or k == 0: \n",
    "                return 0\n",
    "            if i == n-1 and k == 1: \n",
    "                return 1 \n",
    "\n",
    "            # j在此刻作为最大值\n",
    "            res = 0\n",
    "            for t in range(1, j):\n",
    "                res = (res + dfs(i+1, t, k-1)) % mod\n",
    "            # j之前作为最大值\n",
    "            res += j*dfs(i+1, j, k)\n",
    "            return res % mod \n",
    "        \n",
    "        return sum(dfs(0, i, k) for i in range(1, m+1)) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, p, s) :\n",
    "            if i == n :\n",
    "                return 1 if s == k else 0\n",
    "            \n",
    "            res = p * dfs(i+1, p, s) % mod\n",
    "            for j in range(p+1, m+1) :\n",
    "                res = (res + dfs(i+1, j, s+1)) % mod\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        @cache\n",
    "        def f(i: int, mx: int, t: int) -> int:\n",
    "            if i == n: return int(t == k)\n",
    "            r = mx * f(i+1,mx,t) % 1000000007\n",
    "            for x in range(mx+1,m+1):\n",
    "                r += f(i+1,x,t+1)\n",
    "                r %= 1000000007\n",
    "            return r\n",
    "        return f(0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j,cnt):\n",
    "            if i == n:return 1 if cnt == k else 0\n",
    "            ans = j * dfs(i+1,j,cnt)\n",
    "            for x in range(j+1,m+1):\n",
    "                ans += dfs(i+1,x,cnt+1)\n",
    "            return ans % mod\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        @cache\n",
    "        def dp(i, max_so_far, remain):\n",
    "            if i == n:\n",
    "                if remain == 0:\n",
    "                    return 1\n",
    "                \n",
    "                return 0\n",
    "            \n",
    "            ans = (max_so_far * dp(i + 1, max_so_far, remain)) % MOD\n",
    "            for num in range(max_so_far + 1, m + 1):\n",
    "                ans = (ans + dp(i + 1, num, remain - 1)) % MOD\n",
    "                \n",
    "            return ans\n",
    "        \n",
    "        MOD = 10 ** 9 + 7\n",
    "        return dp(0, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        #从i~n-1的位置，并且0~i-1的最大值为max_val, 还需要cost次操作的个数\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, max_val, cost):\n",
    "                \n",
    "            if i == 0:\n",
    "                if cost == 1:\n",
    "                    return 1\n",
    "                return 0                \n",
    "\n",
    "            ans = 0\n",
    "            #前面i-1已经达到了max_val\n",
    "            ans += max_val * dfs(i-1, max_val, cost) % MOD\n",
    "            \n",
    "            if cost > 0:\n",
    "                for val in range(1, max_val):\n",
    "                    ans += dfs(i-1, val, cost - 1) \n",
    "                    ans %= MOD\n",
    "            return ans\n",
    "\n",
    "        p = sum(dfs(n-1, maxVal, k) for maxVal in range(1, m + 1)) % MOD\n",
    "\n",
    "        #dfs.cache_clear()\n",
    "\n",
    "        return p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, max_val, cost):\n",
    "\n",
    "            if cost == 0:\n",
    "                return (max_val ** (n - i)) % MOD\n",
    "\n",
    "            if i == n:\n",
    "                return 0            \n",
    "\n",
    "            ans = 0\n",
    "            ans += dfs(i+1, max_val, cost) * max_val % MOD\n",
    "            for val in range(max_val + 1, m + 1):\n",
    "                ans += dfs(i+1, val, cost - 1) \n",
    "                ans %= MOD\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, 0, k)        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfArrays(self, n: int, m: int, k: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        #从i~n-1的位置，并且0~i-1的最大值为max_val, 还需要cost次操作的个数\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, max_val, cost):\n",
    "            if cost == 1:\n",
    "                return (max_val ** i) % MOD  \n",
    "\n",
    "            if i == 0:\n",
    "                return 0\n",
    "                \n",
    "            ans = 0\n",
    "            #前面i-1已经达到了max_val\n",
    "            ans += max_val * dfs(i-1, max_val, cost) % MOD\n",
    "            \n",
    "            for val in range(1, max_val):\n",
    "                ans += dfs(i-1, val, cost - 1) \n",
    "                ans %= MOD\n",
    "\n",
    "            return ans\n",
    "\n",
    "        p = sum(dfs(n-1, maxVal, k) for maxVal in range(1, m + 1)) % MOD\n",
    "\n",
    "        #dfs.cache_clear()\n",
    "\n",
    "        return p\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
